1. Field of the Invention
This invention relates to databases, and more particularly to a system and method pertaining to hierarchical and relational databases maintained by a computer.
2. Description of the Related Art
Databases of information may be maintained on a computer in a variety of ways to facilitate searching and retrieval of particular data or information records. A database maintained with a hierarchical or "tree" structure--having at least one record as the "root" and other records as "branches" connected to the root--is an intuitive way for people to deal with data records. A hierarchical database can be analogous to nested folders of information: the "root" may be a main folder entitled "Acme Corp.", which may contain as the "branches" folders entitled "Payroll Department", "Accounting Department", and "Manufacturing Department", and each of those folders containing as further "branches" employment records for each employee in a particular department. In a hierarchical database, the root is considered to be at the highest hierarchical level, with other records in subordinate relationships to the root. Thus, a hierarchical database may be said to have a "genealogy", with records having "ancestors" and "descendants", in a particular "consanguinity" (relationship of ancestors and descendants), much as with a family tree.
A hierarchical database is typically used in conjunction with an "index structure", with which records in the hierarchy are assigned to or "indexed" with one or more attributes. The index structure may be used by a computer system to retrieve records in the hierarchy based on a search query given by a user. The index structure uses keywords such as "Company" and "Last Name", each of which contains a keyword value such as "Acme Corp." or "Smith". For example, using systems and methods in the prior art, in order to search for all employees named Smith who work at Acme Corp., all records containing a Last Name must be indexed both by Last Name and by Company. A search query using Boolean algebra is typically used to carry out the search. For the previous example, the search query would be:
Last Name=Smith AND Company=Acme Corp.
A database may also be maintained on a computer in a relational structure. In a relational database, two or more record types have an interrelational dependency: at least one attribute in each of two or more record types takes its values from a common type (or "domain") or values. For example, while one record type for "Department" could include as attributes "Department Code", "Address", and "Phone Number", another record type for "Employee" could include as attributes "Name", "Department Code", and "Home Address". All of the attributes of the record type "Employee" may be related to all of the attributes of the record type "Department" through the common attribute of "Department Code".
While hierarchical databases and relational databases can maintain records containing the same data, each type of database structure has advantages and disadvantages. For example, as noted, a hierarchical database is intuitive for people to deal with, especially when a person searches manually to find a record. However, when implemented on a computer, much more flexible searches are generally possible when the database is relationally structured rather than hierarchically structured.
Specifically, this flexibility comes about from the ability to have as user-selected search criteria any one or more attributes ("keys", "keywords", or "search keys") of any of the records, using any combination of logical or Boolean operators. In order for prior art systems and methods to provide relational search capabilities to hierarchical databases, the index structure would have to duplicate explicitly, for each record, all of the indices of all of that record's ancestors. Because the number of indices that must be examined when analyzing a search inquiry grows exponentially as the number of records grows, the redundancy that would result from implementation of such an index structure soon becomes tremendous, as does the "overhead" of computer resources that would be needed for implementing such an index structure. Therefore, such an implementation is extremely impractical for most hierarchical databases.
It would be desirable to provide a system and method for maintaining a hierarchical database that allows for the flexible searching capabilities of a relational database, while keeping the intuitive advantages of the hierarchical structure and avoiding the problems described above that result from prior art systems and methods. It would also be desirable if such a system and method further provided the capability of allowing a hierarchically structured database to be converted in a computer to a relationally structured database, and vice versa, so that the advantages of either structure could be utilized in various applications.